package problems;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import lib.MathLib;

public class Euler061 extends AbstractEuler {

	Map<Integer, Set<String>> polygonalNumberSets = new HashMap<Integer, Set<String>>();
	
	private static class ChainLink {
		Integer gonality;
		String number;
		ChainLink(Integer gonality, String number) {
			this.gonality = gonality;
			this.number = number;
		}
		
		@Override
		public String toString() {
			return number + "(" + gonality + ")";
		}
		
		public static int getSum(List<ChainLink> chain) {
			int sum = 0;
			for (ChainLink link : chain) {
				sum += Integer.valueOf(link.number);
			}
			return sum;
		}
		
	}
	
	@Override
	public Number calculate() {
	
		//generate and store all 3- through 8-gonal numbers between 1000 and 9999, inclusive
		for (int sides = 3; sides <= 8; sides++) {
			Set<String> sidesGonals = new HashSet<String>();
			for (int i = 1000; i <= 9999; i++) {
				if (MathLib.isPolygonalNumber(i, sides)) {
					sidesGonals.add(String.valueOf(i));
				}
			}
			polygonalNumberSets.put(sides, sidesGonals);
		}
		
		//start searching with the smallest set
		Set<String> start = polygonalNumberSets.get(8);
		
		//recursively attempt to find a path connecting a chosen starting number, through
		//each n-gonal group, back to itself.
		for (String eightGonal : start) {
			List<ChainLink> chain = new ArrayList<ChainLink>();
			chain.add(new ChainLink(8,eightGonal));
			if (leadsBackToStart(chain)) {
//				System.out.println("found a circular chain: " + chain);
				return ChainLink.getSum(chain);
			}
		}
		
		fail("no result found");
		return null;
	}
	
	private boolean leadsBackToStart(List<ChainLink> chain) {
		if (chain.size() == 6) {
			return chain.get(0).number.startsWith(chain.get(5).number.substring(2));
		}
		
		Set<Integer> visitedSets = new HashSet<Integer>();
		Set<String> visitedNumbers = new HashSet<String>();
		for (ChainLink link : chain) {
			visitedSets.add(link.gonality);
			visitedNumbers.add(link.number);
		}
		
		for (Entry<Integer, Set<String>> anotherSet : polygonalNumberSets.entrySet()) {
			if (visitedSets.contains(anotherSet.getKey())) continue;
			for (String candidateNumber: anotherSet.getValue()) {
				if (visitedNumbers.contains(candidateNumber)) continue;
				if (!candidateNumber.startsWith(chain.get(chain.size() - 1).number.substring(2))) continue;
				ChainLink candidateLink = new ChainLink(anotherSet.getKey(), candidateNumber);
				chain.add(candidateLink);
				if (leadsBackToStart(chain)) {
					return true;
				} else {
					chain.remove(candidateLink);
				}
			}
		}
		return false;
		
	}

	@Override
	protected Number getCorrectAnswer() {
		return 28684;
	}

}
